//滑动窗口的平均值
class MovingAverage {
public:
    /** Initialize your data structure here. */

    //用队列进行模拟实现
    //先进先出符合要求，用数组需要一直扩容？
    //或者一直进行头删操作 比较麻烦 所以使用底层是deque的队列
    MovingAverage(int size) 
        :_size(size)
        ,_sum(0)
    {}
    double next(int val) 
    {
        if(_q.size()==_size)
        {
            _sum-=_q.front();
            _q.pop();
        }
        _q.push(val);
        _sum+=val;
        return _sum/_q.size();
    }

private:
    queue<int>_q;
    int _size;
    //每次计算平均值都需要知道总和 用一个变量表示它
    double _sum;
};

//最近请求次数
class RecentCounter {
public:
    //用队列， 将如果队头元素小于当前元素-3000 则pop掉 然后返回队列大小
    RecentCounter() 
    {}
    
    int ping(int t) 
    {
        q.push(t);
        while(!q.empty() && (t-3000)>q.front() )
        {
            q.pop();
        }
        return q.size();
    }
private:
    queue<int>q;
};
//往完全二叉树添加节点
class CBTInserter {
public:
    CBTInserter(TreeNode* root) 
    {
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty())
        {
            TreeNode* cur=q.front();
            q.pop();
            _v.push_back(cur);
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }

    }
    
    int insert(int v) 
    {
        //0 -> 1 and 2
        //1-> 3 and 4  2-> 5 and 6 father=(child-1)/2
        TreeNode* newnode=new TreeNode(v);
        _v.push_back(newnode);
        int child=_v.size()-1;
        int father=(child-1)/2;
        TreeNode* parent=_v[father];
        if(child%2==1)
        {
            parent->left=newnode;
        }
        else
        {
            parent->right=newnode;
        }
        return parent->val;
    }
    
    TreeNode* get_root() 
    {
        return _v[0];
    }
private:
    vector<TreeNode*> _v;
};

//矩阵中的距离
class Solution {
public:
    int arr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) 
    {
        int m=mat.size();
        int n=mat[0].size();
        vector<vector<bool>>used(m,vector<bool>(n,false));
        vector<vector<int>>res(m,vector<int>(n,0));
        queue<pair<int,int>>q;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(mat[i][j]==0)
                {
                    q.push(make_pair(i,j));
                    used[i][j]=true;
                }
            }
        }
        while(!q.empty())
        {
            pair<int,int>p=q.front();
            q.pop();
            for(int i=0;i<4;i++)
            {
                int nx=p.first+arr[i][0];
                int ny=p.second+arr[i][1];
                if(nx<0 ||nx>=m ||ny<0||ny>=n ||used[nx][ny])continue;
                q.push(make_pair(nx,ny));
                used[nx][ny]=true;
                res[nx][ny]=res[p.first][p.second]+1;
            }
        }
        return res;
    }
};
//二叉树中每层的最大值
class Solution {
public:
    vector<int> largestValues(TreeNode* root) 
    {
        vector<int>res;
        if(!root) return res;
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();
            int tmpmax=INT_MIN;
            while(size--)
            {
                TreeNode* cur=q.front();
                q.pop();
                tmpmax=(cur->val)>tmpmax?cur->val:tmpmax;
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            res.push_back(tmpmax);
        }
        return res;
    }
};
//二叉树中最底层最左边的值
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) 
    {
        int res=root->val;
        int maxdeep=0;
        dfs(root,0,maxdeep,res);
        return res;
    }
    void dfs(TreeNode*cur, int curdeep,int& maxdeep,int& res)
    {
        if(!cur->left && !cur->right)
        {
            if(curdeep>maxdeep)
            {
                maxdeep=curdeep;
                res=cur->val;
            }
            return;
        } 
        if(cur->left)
        {
            dfs(cur->left,curdeep+1,maxdeep,res);
        }
        if(cur->right)
        {
            dfs(cur->right,curdeep+1,maxdeep,res);
        }
    }
};

//二叉树的右视图
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) 
    {
        vector<int>res;
        if(!root) return res;
        int maxdeep=-1;
        dfs(root,0,maxdeep,res);
        return res;
    }
    void dfs(TreeNode* cur,int curdeep,int&maxdeep,vector<int>&res)
    {
        if(!cur) return;
        if(curdeep>maxdeep)
        {
            res.push_back(cur->val);
            maxdeep=curdeep;
        }
        dfs(cur->right,curdeep+1,maxdeep,res);
        dfs(cur->left,curdeep+1,maxdeep,res);
    }
};

//二叉树剪枝
class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) 
    {
        //因为要判断一个树的左右子树是不是都是0值 并且没有孩子
        //所以采用后序遍历
        if(!root) return nullptr;
        TreeNode*left=pruneTree(root->left);
        TreeNode* right=pruneTree(root->right);
        if(root->val==0 && !left && !right)
        {
            return nullptr;
        }
        root->left=left;
        root->right=right;
        return root;
    }
};